#include <setjmp.h>
#include <signal.h>
#include <errno.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <sys/time.h>
#include <unistd.h>
#include <map>
#include <list>
#include <math.h>
#include <errno.h>
#include "uthreads.hh"

#include "translate_address.hh"

#define MILLION 1000000
using namespace std;

sigset_t SIGVTALRM_set;
void reschedule();

const char *SYSERR = "system error: ";
const char *LIBERR = "thread library error: ";


enum state { RUNNING, READY, SLEEPING, SYNCHING };
struct thread_data_t {
    thread_data_t() { stack = new char[STACK_SIZE]; }
    ~thread_data_t() { delete[] stack; }
  int thread_id;
  char *stack;
  sigjmp_buf jbuf;

  int state;
  int sync_id;//valid only if SYNCHING
};

class sigblock_t {
public:
  sigblock_t()
  { if (sigprocmask(SIG_BLOCK, &SIGVTALRM_set, &oldmask) != 0) {
      fprintf(stderr,"%ssigprocmask failed\n", SYSERR);
      exit(1);
    }
  }
  ~sigblock_t()
  { if (sigprocmask(SIG_SETMASK, &oldmask, NULL) != 0) {
      fprintf(stderr,"%ssigprocmask failed\n", SYSERR);
      exit(1);
    }
  }
private:
  sigset_t oldmask;
};


typedef map<int, thread_data_t *> threadmap_t;
typedef map<int, threadmap_t *> syncmap_t;

static threadmap_t _idMap;

static threadmap_t _readyMap;
static syncmap_t _syncWaits;
static map<int, int> _syncNums; //sync_id ==> num
static thread_data_t *_sleepingThread; //NULL if none
static thread_data_t *_runningThread;
static thread_data_t *_threadToDelete;

static int _nextTid;
int getNextTID()
{
  int ret = _nextTid;
  ++_nextTid;
  return ret;
}



void timerExpired(int)
{
    //    printf("expired %lx\n", _sleepingThread);
  if (_sleepingThread == NULL) {
    fprintf(stderr, "%sstrange - no sleeping thread and timer expired\n", LIBERR);
    return;
  }
  
  //resume sleeping thread
  _sleepingThread->state = READY;
  _readyMap[_sleepingThread->thread_id] = _sleepingThread;
  _sleepingThread = NULL;

  reschedule(); //will return the next time the thread is running
}



//assumption: on entry SIGVTALRM is blocked.
//assumption: on entry, if running thread state is "RUNNING" then it is allowed to run. otherwise it is either terminated (NULL) or not ready.
void reschedule()
{

  thread_data_t *candidateThread = (--_readyMap.end())->second;

  if ((_runningThread != NULL) && (_runningThread->state == RUNNING) &&
      (candidateThread->thread_id < _runningThread->thread_id))
    //no need to reschedule
    return;
  if (_runningThread != NULL) {
    if (_runningThread->state == RUNNING) {
      _readyMap[_runningThread->thread_id] = _runningThread;
      _runningThread->state = READY;
    }
    int ret_val = sigsetjmp(_runningThread->jbuf,1);
    if (ret_val == 1) {
      if (_threadToDelete != NULL)
        delete _threadToDelete;
      return;
    }
  }

  //schedule first ready thread
  _runningThread = candidateThread;
  _readyMap.erase(candidateThread->thread_id);
  _runningThread->state = RUNNING;
  siglongjmp(_runningThread->jbuf,1);  
}


/* Initialize thread library */
int thread_lib_init()
{
  sigemptyset(&SIGVTALRM_set);
  sigaddset(&SIGVTALRM_set, SIGVTALRM);

  _runningThread = new thread_data_t(); //the main thread
  _threadToDelete = NULL;  
  _idMap[0] = _runningThread;
  _runningThread->thread_id = 0;
  _runningThread->state = RUNNING;
    delete _runningThread->stack;
    _runningThread->stack = NULL;
  _nextTid = 1;

  //attach the signal handler
  int ret;
  struct sigaction new_action;
  new_action.sa_handler = timerExpired;
  new_action.sa_mask = SIGVTALRM_set;
  new_action.sa_flags = 0;

  ret = sigaction(SIGVTALRM, &new_action, NULL);

  if (ret != 0) {
    exit(1);
  }

  
  return 0;
}

/* Create a new thread whose entry point is f */
int thread_spawn(void (*f)(void))
{
  sigblock_t block; //blocks signals
  
  
  thread_data_t *th = new thread_data_t();
  address_t sp = (address_t)th->stack + STACK_SIZE - sizeof(address_t); 
  address_t pc = (address_t)f;

  sigset_t set;
  sigprocmask(SIG_SETMASK, NULL, &set);
  sigdelset(&set, SIGVTALRM);

  sigsetjmp(th->jbuf,1);
  ((th->jbuf)->__jmpbuf)[JB_SP] = translate_address(sp);
  ((th->jbuf)->__jmpbuf)[JB_PC] = translate_address(pc);
  (th->jbuf)->__saved_mask = set;

  th->thread_id = getNextTID();
  _readyMap[th->thread_id] = th;
  th->state = READY;
  _idMap[th->thread_id] = th;
  reschedule();
  return th->thread_id;
}

/* Terminate a thread */
int thread_terminate(int tid)
{
  sigblock_t block; //blocks signals

  if (tid == 0) {
    exit(0);
  }
  
  map<int, thread_data_t *>::iterator iter = _idMap.find(tid);
  if (iter == _idMap.end()) {
    fprintf(stderr,"%sTried to terminate a nonexisting thread\n", LIBERR);
    return -1;
  }
  thread_data_t *th = iter->second;
  _idMap.erase(tid);
  switch (th->state) {
   case RUNNING:
     delete _runningThread;
     _runningThread = NULL;
     
     reschedule(); //does not return
     break;

   case READY:
    _readyMap.erase(th->thread_id);
    delete th;
    break;
   case SLEEPING:
     delete _sleepingThread;
     _sleepingThread = NULL;
     //reset the timer
     struct itimerval tv;
     tv.it_value.tv_sec = 0; //time of first timer
     tv.it_value.tv_usec = 0; //time of first timer
     tv.it_interval.tv_sec = 0; //time of all timers but the first one
     tv.it_interval.tv_usec = 0; //time of all timers but the first one

     {
         
       int ret = setitimer(ITIMER_VIRTUAL, &tv, NULL);
       if (ret != 0) {
         fprintf(stderr, "%ssetitimer failed\n", SYSERR);
         exit(1);
       }
     }

     break;
   case SYNCHING:
     _syncWaits[th->sync_id]->erase(th->thread_id);
     if (_syncWaits[th->sync_id]->empty()) {
       _syncWaits.erase(th->sync_id);
       _syncNums.erase(th->sync_id);
     }
     delete th;
     break;
  }
  return 0;
}

/* Get thread id */
int thread_gettid()
{
  return _runningThread->thread_id;
}


/* Synchronize threads */
int thread_sync(int sync_id, int num)
{
  //block signals
  sigblock_t block;

  if (_runningThread->thread_id == 0) {
    fprintf(stderr, "%sTried to synch the main thread\n",LIBERR);
    return -1;
  }
  
  if (num < 2) {
    fprintf(stderr, "%sTried to synch less than 2 threads\n",LIBERR);
    return -1;
  }
  
  syncmap_t::iterator iter =  _syncWaits.find(sync_id);

  if (iter == _syncWaits.end()) {
    threadmap_t *tmap = new threadmap_t();
    _syncWaits[sync_id] = tmap;
    (*tmap)[_runningThread->thread_id] = _runningThread;
    _syncNums[sync_id] = num;
    _runningThread->state = SYNCHING;
    _runningThread->sync_id = sync_id;
    reschedule(); //will return when sync is done
  } else {
    if (_syncNums[sync_id] != num) {
      fprintf(stderr, "%sTried to sync another thread with a different num\n",
            LIBERR);
      return -1;
    }
    if (iter->second->size() < (num-1)) {
      //add to synch list and change state
      (*iter->second)[_runningThread->thread_id] = _runningThread;
      _runningThread->state = SYNCHING;
      _runningThread->sync_id = sync_id;
      reschedule(); //will return when sync is done
    } else {
      //release all others
      for(threadmap_t::iterator thiter = iter->second->begin();
          thiter != iter->second->end(); ++thiter) {
        thiter->second->state = READY;
        _readyMap[thiter->second->thread_id] = thiter->second;
      }
      delete iter->second;
      _syncWaits.erase(iter);
      _syncNums.erase(sync_id);
      reschedule(); //perhaps another thread should run now
    }       
  }

  return 0;
  //unblock signals
}

/* Sleep */
int thread_sleep(int tid, int num_millisecs)
{
  //block signals
  sigblock_t block;


  if (tid == 0) {
    fprintf(stderr,"%sTried to sleep with the main thread\n", LIBERR);
    return -1;
  }

  if (_sleepingThread != NULL) {
    fprintf(stderr, "%sTried to sleep more than one thread\n", LIBERR);
    return -1;
  }


  if (num_millisecs <= 0) {
      fprintf(stderr, "%sTried to sleep with a nonpositive number of milliseconds\n", LIBERR);
      return -1;
  }
  map<int, thread_data_t *>::iterator iter = _idMap.find(tid);
  if (iter == _idMap.end()) {
    fprintf(stderr,"%sTried to sleep a nonexisting thread\n", LIBERR);
    return -1;
  }
  
  thread_data_t *th = iter->second;

  if (th->state == SYNCHING) {
    fprintf(stderr, "%sTried to sleep a synching thread\n", LIBERR);
    return -1;
  }

  if (th->state == READY) {
    _readyMap.erase(th->thread_id);
  } else {
    if (th->state != RUNNING) {//"assert"
      exit(17);
    }
  }
  th->state = SLEEPING;
  _sleepingThread = th;
  
  //set the timer here
  struct itimerval tv;
  tv.it_value.tv_sec = num_millisecs/1000; //time of first timer
  tv.it_value.tv_usec = (num_millisecs % 1000) * 1000; //time of first timer
  tv.it_interval.tv_sec = 0; //time of all timers but the first one
  tv.it_interval.tv_usec = 0; //time of all timers but the first one

  int ret = setitimer(ITIMER_VIRTUAL, &tv, NULL);
  int myerr = errno;
  if (ret != 0) {
      fprintf(stderr, "%ssetitimer failed: %s\n", SYSERR, strerror(myerr));
    exit(1);
  }

  reschedule();

  return 0;
  //unblock signals
}


int thread_get_time_until_wakeup(int tid)
{
    sigblock_t block;
    map<int, thread_data_t *>::iterator iter = _idMap.find(tid);
    if (iter == _idMap.end()) {
        return 0;
    }
    if (iter->second->state != SLEEPING) {
        return 0;
    }
    
    struct itimerval tv;
    int ret = getitimer(ITIMER_VIRTUAL, &tv);
    if (ret != 0) {
        fprintf(stderr, "%sgetitimer failed\n", SYSERR);
        exit(1);
    }

    return tv.it_value.tv_sec * 1000 + ceil(double(tv.it_value.tv_usec)/1000);
}

int thread_get_num_waiting_for_sync(int sync_id)
{
  sigblock_t block;
  syncmap_t::iterator iter =  _syncWaits.find(sync_id);
  if (iter == _syncWaits.end()) {
	return 0;
  }

  return iter->second->size();
}

